เมนูนำทาง
Dynamic time warping ขั้นตอนวิธีเป้าหมายของไดนามิกไทม์วอร์ปปิง คือ เพื่อเปรียบเทียบลำดับที่ขึ้นอยู่กับเวลาสองชุด
X := ( x 1 , x 2 , . . . , x N ) {\displaystyle X:=(x_{1},x_{2},...,x_{N})\,} ด้วยความยาว N {\displaystyle N\,} ซึ่งเป็นจำนวนเต็ม Y := ( y 1 , y 2 , . . . , y M ) {\displaystyle Y:=(y_{1},y_{2},...,y_{M})\,} ด้วยความยาว M {\displaystyle M\,} ซึ่งเป็นจำนวนเต็มโดยลำดับเหล่านี้อาจจะเป็นสัญญาณที่ไม่ต่อเนื่อง (อนุกรมเวลา) หรือ ลำดับของลักษณะเฉพาะ (feature) ที่ถูกสร้างขึ้นตามช่วงเวลา กำหนดให้ปริภูมิของลักษณะเฉพาะแทนด้วย F {\displaystyle F\,} ดังนั้น x n , y m ∈ F {\displaystyle x_{n},y_{m}\in F} สำหรับ n ∈ [ 1 : N ] {\displaystyle n\in [1:N]} และ m ∈ [ 1 : M ] {\displaystyle m\in [1:M]} เพื่อที่จะเปรียบเทียบลักษณะเฉพาะ x , y ∈ F {\displaystyle x,y\in F} จึงจำเป็นที่จะต้องคำนวณต้นทุนเฉพาะส่วน (local cost measure) หรือเรียกอีกอย่างได้ว่า การคำนวณระยะทางเฉพาะส่วน (local distance measure) ซึ่งนิยามได้เป็นฟังก์ชัน c : F × F → R ⩾ 0 {\displaystyle c:F\times F\rightarrow R\geqslant 0} ซึ่งโดยทั่วไป c ( x , y ) {\displaystyle c(x,y)\,} จะมีค่าน้อย ถ้า x {\displaystyle x\,} และ y {\displaystyle y\,} มีความคล้ายกันมาก ซึ่งสำหรับแต่ละคู่ของลำดับทั้งสอง นำไปสร้าง เมทริกซ์ต้นทุน (cost matrix) C ∈ R N × M {\displaystyle C\in R^{N\times M}} นิยามด้วย C ( n , m ) := c ( x n , y m ) {\displaystyle C(n,m):=c(x_{n},y_{m})\,} ดังรูป
โดยเป้าหมายต่อไปคือการหาวิถีการปรับแนวระหว่าง X {\displaystyle X\,} และ Y {\displaystyle Y\,} ที่มีต้นทุนรวมน้อยที่สุด โดยปกติแล้ว วิถีการปรับแนว จะวิ่งไปตามทางที่ต้นทุนต่ำภายในเมทริกซ์ต้นทุน ด้วยรูปแบบดังนี้
เส้นทางบิดเบือน ( N , M ) {\displaystyle (N,M)\,} เป็นลำดับ p = ( p 1 , . . . , p L ) {\displaystyle p=(p_{1},...,p_{L})\,} และ p l = ( n l , m l ) ∈ [ 1 : N ] × [ 1 : M ] {\displaystyle p_{l}=(n_{l},m_{l})\in [1:N]\times [1:M]} สำหรับ l ∈ [ 1 : L ] {\displaystyle l\in [1:L]} จะสนใจเงื่อนไขดังต่อไปนี้
ซึ่งจะได้ตัวอย่างของเส้นทางบิดเบือนแบบต่างๆภายใต้เงื่อนไขดังรูป
เส้นทางการบิดเบือนภายใต้เงื่อนไขแบบต่างๆโดยต้นทุนทั้งหมดของเส้นทางบิดเบือน p {\displaystyle p\,} ระหว่าง X {\displaystyle X\,} และ Y {\displaystyle Y\,} ซึ่งเกี่ยวเนื่องกับการวัดต้นทุนเฉพาะส่วน c {\displaystyle c\,} จะถูกนิยามด้วย
c p ( X , Y ) := ∑ l = 1 L c ( x n l , y n l ) {\displaystyle c_{p}(X,Y):=\sum _{l=1}^{L}c(x_{n_{l}},y_{n_{l}})}
สำหรับ เส้นทางบิดเบือนที่เหมาะสมระหว่าง X {\displaystyle X\,} และ Y {\displaystyle Y\,} คือระยะทางบิดเบือน p ′ {\displaystyle p'\,} ซึ่งมีต้นทุกต่ำที่สุดเมื่อเทียบกับเส้นทางบิดเบือนทั้งหมดที่เป็นไปได้ ระยะทางไดนามิกไทม์วอร์ปปิง D T W ( X , Y ) {\displaystyle DTW(X,Y)\,} ระหว่าง X {\displaystyle X\,} และ Y {\displaystyle Y\,} จะถูกนิยามเป็นต้นทุนทั้งหมดของ p ′ {\displaystyle p'\,} โดย
D T W ( X , Y ) {\displaystyle DTW(X,Y)\,} | := c p ′ ( X , Y ) {\displaystyle :=c_{p'}(X,Y)\,} |
= m i n { c p ( X , Y ) | p {\displaystyle =min\{c_{p}(X,Y)|p\,} เป็นเส้นทางบิดเบือน ( N , M ) } {\displaystyle (N,M)\}\,} |
ซึ่งสุดท้ายแล้วจะได้ระยะทางบิดเบือนที่เหมาะสมดังรูป
เมนูนำทาง
Dynamic time warping ขั้นตอนวิธีใกล้เคียง
แหล่งที่มา
WikiPedia: Dynamic time warping http://kinectdtw.codeplex.com/ http://code.google.com/p/lbimproved/ http://dtw.r-forge.r-project.org/ http://www.eng.chula.ac.th/newsletter/index.php?q=... https://mlpy.fbk.eu/